/**
 * 一个数组，如果其中没有逆序对，就称为稳定的
 * 给定一个数组，以及若干次询问，每次问A[L, R]内的稳定子数组的数量是多少个
 * 
 * 没有逆序对，说明数组是不严格递增的，假设稳定数组最长为n，则其中所有稳定子数组的数量是(n + 1) * n / 2
 * 因此本质就是要问[L, R]之间有多少段不严格递增区间，每一段的长度各是多少
 * 注意到使用分治，只需要再记录左右边界值、左右边界长度、总长度与答案即可
 * 可以在O(1)的时间合并，因此使用线段树完成
 * 
 * 注意到没有修改操作，因此其实可以使用前缀和完成，比线段树编码量小
 * 
 */
vector<int>::const_iterator SourceIt;

struct SegTree{ // 线段树带延迟

using llt = long long;

struct _t{
    int left_bound;
    int right_bound;
    int left_len;
    int right_len;
    int total_len;
    llt ans;
    _t() = default;
    _t(int x): left_bound(x), right_bound(x), left_len(1), right_len(1), total_len(1), ans(1){}
    _t(int a, int b, int c, int d, int e, llt f): left_bound(a), right_bound(b), left_len(c), right_len(d), total_len(e), ans(f){}
    bool isNone() const {
        if(-1 == left_bound){
            assert(-1 == right_bound and -1 == left_len and -1 == right_len and -1 == total_len and -1 == ans);
            return true;
        }
        return false;
    }
};

int N;

using value_type = _t;
vector<value_type> data; // 线段树

using lazy_type = llt;
vector<lazy_type> lazy; // 延迟标记

/// 从下往上计算信息，要变动
value_type _up_(const value_type & ls, const value_type & rs) {
    if(ls.isNone()) return rs;
    if(rs.isNone()) return ls;

    if(ls.right_bound > rs.left_bound){
        return {ls.left_bound, rs.right_bound, ls.left_len, rs.right_len, ls.total_len + rs.total_len, ls.ans + rs.ans};
    }
    // 左边贯通
    if(ls.left_len == ls.total_len){
        assert(ls.right_len == ls.total_len);
        if(rs.left_len == rs.total_len){ // 右边也贯通
            assert(rs.right_len == rs.total_len);
            int n = ls.total_len + rs.total_len;
            return {ls.left_bound, rs.right_bound, n, n, n, (n + 1LL) * n / 2LL};
        }
        
        // 右边不通
        int n = ls.total_len + rs.left_len;
        return {ls.left_bound, rs.right_bound, n, rs.right_len, ls.total_len + rs.total_len, rs.ans - (rs.left_len + 1LL) * rs.left_len / 2LL + (n + 1LL) * n / 2LL};
        
    }

    // 左边不通
    if(rs.left_len == rs.total_len){
        assert(rs.right_len == rs.total_len);
        int n = ls.right_len + rs.total_len;
        return {ls.left_bound, rs.right_bound, ls.left_len, n, ls.total_len + rs.total_len, ls.ans - (ls.right_len + 1LL) * ls.right_len / 2LL + (n + 1LL) * n / 2LL};
    }

    // 都不通   
    int x = ls.right_len, y = rs.left_len;
    int n = x + y;
    return {ls.left_bound, rs.right_bound, ls.left_len, rs.right_len, ls.total_len + rs.total_len, ls.ans + rs.ans - (x + 1LL) * x / 2LL - (y + 1LL) * y / 2LL + (n + 1LL) * n / 2LL};
}

// 根据变动信息delta计算本节点的信息并且打延迟标记，用于pushDown或者modify
// 这里只计算t，跟t的儿子无关
// 要计算data[t]和lazy[t]
void _dn_(int t, int s, int e, const lazy_type & delta) {
    assert(0);
}

/// 初始化，清零，不用动
void init(int n) {
    data.assign((N = n) + 1 << 2, value_zero());
    lazy.assign(n + 1 << 2, lazy_zero());
}

/// 这个函数不用动
void modify(int a, int b, const lazy_type & delta){
    _modify(1, 1, N, a, b, delta);
}

/// 这个函数不用动
value_type query(int a, int b){
    return _query(1, 1, N, a, b);
}

/// 这个函数不用动
void build() {
    _build(1, 1, N);
}

/// 几乎不用动
value_type _query(int t, int s, int e, int a, int b) {
    if(a <= s and e <= b) {
        return data[t];
    }
    _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    value_type ans = value_zero(); // 如果求最值，这里不能用zero
    if(a <= mid) ans = _up_(ans, _query(lson(t), s, mid, a, b));
    if(mid < b) ans = _up_(ans, _query(rson(t), mid + 1, e, a, b));
    return ans;
}

/// 几乎不用动
void _modify(int t, int s, int e, int a, int b, const lazy_type & delta) {
    if(a <= s and e <= b) {
        _dn_(t, s, e, delta);
        return;
    }
    _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    if(a <= mid) _modify(lson(t), s, mid, a, b, delta);
    if(mid < b) _modify(rson(t), mid + 1, e, a, b, delta);
    _pushUp(t);
    return;
}

/// 这个函数不用动
void _pushUp(int t) {
    data[t] = _up_(data[lson(t)], data[rson(t)]);
}

/// 这个函数几乎不用动
void _pushDown(int t, int s, int e) {
    if(lazy_zero() == lazy[t]) return;
    auto & lz = lazy[t];
    auto ls = lson(t), rs = rson(t);
    int mid = (s + e) >> 1;

    _dn_(ls, s, mid, lz);
    _dn_(rs, mid + 1, e, lz);

    lz = lazy_zero();
}


/// 几乎不用动
void _build(int t, int s, int e) {
    if(s == e) {
        int x = *SourceIt++;
        data[t] = value_type(x); // 注意提供value_type的初始化
        return; 
    }
    int mid = (s + e) >> 1;
    _build(lson(t), s, mid);
    _build(rson(t), mid + 1, e);
    _pushUp(t);
}

/// 辅助函数，视延迟的类型而变动
static const lazy_type & lazy_zero() {
    static const lazy_type LAZY0 = 0;
    return LAZY0; 
}

/// 辅助函数，视线段树信息类型而变动
static const value_type & value_zero() {
    static const value_type VALUE0 = {-1, -1, -1, -1, -1, -1LL};
    return VALUE0;
}

/// 这两个函数不用变动
static int lson(int x) {return x << 1;}
static int rson(int x) {return lson(x) | 1;}


};

int N;
SegTree St;

class Solution {
public:
    vector<long long> countStableSubarrays(vector<int>& nums, vector<vector<int>>& queries) {
        N = nums.size();
        SourceIt = nums.begin();
        St.init(N);
        St.build();

        vector<long long> ans;
        for(const auto & vec : queries){
            int a = vec[0] + 1;
            int b = vec[1] + 1;
            auto t = St.query(a, b);
            ans.emplace_back(t.ans);
        }
        return ans;
    }
};
